//
//  TraceNodeMaker.m
//  Conference Track Management
//
//  Created by Jiang on 2018/10/22.
//  Copyright © 2018 jiang. All rights reserved.
//

#import "TraceNodeMaker.h"

@interface TraceNodeMaker()

@end

@implementation TraceNodeMaker
- (int **)generateMatrix{
    int **matrix = malloc(sizeof(int *) * (_talks.count + 1));
    for (int i = 0; i < _talks.count + 1; i++) {
        size_t len = sizeof(int) * (self.maxDuration + 1);
        matrix[i] = malloc(len);
        memset(matrix[i], 0, len);
    }
    matrix[0][0] = 1;
    for (int i = 1; i < _talks.count + 1; i++) {
        for (int j = 0; j < self.maxDuration + 1; j++) {
            int duration = _talks[i - 1].duration;
            if (duration <= j)
                matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - duration];
            else
                matrix[i][j] = matrix[i - 1][j];
        }
    }
    return matrix;
}
- (instancetype)initWithMin:(int)minDuration max:(int)maxDuration talks:(NSArray<id <Talk>> *)talks{
    self = [super init];
    NSAssert(maxDuration >= minDuration, @"maxDuration >= minDuration");
    NSAssert(minDuration >= 0, @"minDuration >= 0");
    NSAssert(maxDuration >= 0, @"maxDuration >= 0");
    self.minDuration = minDuration;
    self.maxDuration = maxDuration;
    _talks = talks;
    _matrix = [self generateMatrix];
    return self;
}
- (NSArray<TraceNode *> *)traceNodes{
    if (!_traceNodes) {
        if (_talks.count == 0 || self.totalSchemeCount == 0) {
            return @[];
        }
        NSMutableArray *traceNodes = [NSMutableArray array];
        for (int time = self.minDuration; time <= self.maxDuration; time++) {
            if ([self schemeCountForTime:time] <= 0) {
                continue;
            }
            NSMutableArray * nodes = [NSMutableArray array];
            [self lookBackToGetAllTrace:time num:_talks.count last:nil traces:nodes];
            [traceNodes addObjectsFromArray:nodes];
        }
        _traceNodes = [traceNodes copy];
    }
    return _traceNodes;
}

- (int)schemeCountForTime:(int)time{
    return _matrix[_talks.count][time];
}
- (int)totalSchemeCount{
    int count = 0;
    for (int i = self.minDuration; i <= self.maxDuration; i++) {
        count += [self schemeCountForTime:i];
    }
    return count;
}
- (void)lookBackToGetAllTrace:(int)duration num:(NSUInteger)num last:(TraceNode *)last traces:(NSMutableArray *)traces{
    if (num == 0)
        return;
    
    id <Talk> talk = _talks[num - 1];
    int uncluded = _matrix[num - 1][duration];
    int included = _matrix[num - 1][duration - talk.duration];
    if (uncluded > 0)
        [self lookBackToGetAllTrace:duration num:num - 1 last:last traces:traces];
    if (included > 0){
        int nextDuration = duration - talk.duration;
        TraceNode * node = [[TraceNode alloc] initWithTalk:talk lastNode:last];
        if (nextDuration == 0){
            [traces addObject:node];
            return;
        }
        [self lookBackToGetAllTrace:nextDuration num:num - 1 last:node traces:traces];
    }
}
- (void)dealloc{
    for (int i = 0; i < _talks.count + 1; i++) {
        free(_matrix[i]);
    }
    free(_matrix);
}
@end
